package org.example.day;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @Description: Solution56
 * @Author wyatt
 * @Data 2024/06/24 21:56
 */
public class Solution56 {

    public static void main(String[] args) {
        Solution56 solution = new Solution56();
        int[][] result = solution.merge(new int[][]{{1,2},{3,5},{2,4}});
    }

    public int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        //先确定是可以合并 i右区间 > i+1 左区间， 合并的话， 右区间取大
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> range = new ArrayList<>();
        range.add(intervals[0][0]);
        range.add(intervals[0][1]);
        list.add(range);
        for (int i = 1; i < intervals.length; i++) {
            int leftMax = list.get(list.size() - 1).get(1);
            int rightMin = intervals[i][0];

            if(leftMax >= rightMin){
                //合并
                list.get(list.size() - 1).set(1, Math.max(list.get(list.size() - 1).get(1), intervals[i][1]));
            }else {
                //不合并
                List<Integer> range2 = new ArrayList<>();
                range2.add(intervals[i][0]);
                range2.add(intervals[i][1]);
                list.add(range2);
            }
        }

        int[][] result = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            result[i][0] = list.get(i).get(0);
            result[i][1] = list.get(i).get(1);
        }

        return result;
    }

}
